// 2025/3/9
// https://leetcode.cn/problems/lru-cache/?envType=study-plan-v2&envId=top-100-liked
// LRU缓存

class LRUCache {
    public:
        struct ListNode{
            ListNode(int key = 0, int value = 0, ListNode* prev = nullptr, ListNode* next = nullptr)
                :_kv(key, value)
                ,_prev(prev)
                ,_next(next)
            {}
    
            ListNode* _prev;
            ListNode* _next;
            pair<int, int> _kv;
        };
    
        LRUCache(int capacity) 
            :_capacity(capacity)
            ,_size(0)
            ,_head(new ListNode)
            ,_tail(new ListNode)
        {
            _head->_next = _tail;
            _tail->_prev = _head;
        }
        
        int get(int key) {
            if(_mp.count(key))
            {
                ListNode* ret = _mp[key];
                if(ret->_prev)
                    ret->_prev->_next = ret->_next;
                if(ret->_next)
                    ret->_next->_prev = ret->_prev;
    
                ret->_next = _tail;
                ret->_prev = _tail->_prev;
                ret->_prev->_next = ret;
                _tail->_prev = ret;
    
                return ret->_kv.second;
            }
            return -1;
        }
        
        void put(int key, int value) {
            if(_mp.count(key))
            {
                _mp[key]->_kv.second = value;
                get(key);
            }
            else
            {
                // 新结点插到最后
                ListNode* newnode = new ListNode(key, value);
                _mp.emplace(key, newnode);
                get(key);
                _size++;
            }
    
            // 超了，删掉队头
            if(_size > _capacity)
            {
                ListNode* del = _head->_next;
                _head->_next = del->_next;
                _head->_next->_prev = _head;
                _mp.erase(del->_kv.first);
                delete del;
                _size--;
            }
        }
    
        ~LRUCache()
        {
            while(_head != nullptr)
            {
                ListNode* tmp = _head;
                _head = _head->_next;
                delete tmp;
            }
        }
    
        int _capacity;
        int _size;
        unordered_map<int, ListNode*> _mp;
        ListNode* _head;
        ListNode* _tail;
    };
    
    /**
     * Your LRUCache object will be instantiated and called as such:
     * LRUCache* obj = new LRUCache(capacity);
     * int param_1 = obj->get(key);
     * obj->put(key,value);
     */